import java.util.Arrays;

public class LeetCode733 {
    public static void main(String[] args) {
        int[][] img = {
                {1, 1, 1},
                {1, 1, 0},
                {1, 0, 1},
        };
        int[][] res = floodFill(img, 1, 1, 2);

        for (int i = 0; i < res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }
    }

    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor == newColor) {
            return image;
        }

        dfsColor(image, sr, sc, oldColor, newColor);

        return image;
    }

    private static void dfsColor(int[][] image, int sr, int sc, int oldColor, int newColor) {
        if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[sr].length || image[sr][sc] != oldColor) {
            return;
        }

        image[sr][sc] = newColor;

        dfsColor(image, sr + 1, sc, oldColor, newColor);
        dfsColor(image, sr - 1, sc, oldColor, newColor);
        dfsColor(image, sr, sc + 1, oldColor, newColor);
        dfsColor(image, sr, sc - 1, oldColor, newColor);
    }
}
